翻訳と辞書 Words near each other ・ Sardhana (Assembly constituency) ・ Sardhana, Medak ・ Sardheri ・ Sardi ・ Sardi (musician) ・ Sardi's ・ Sardi, Ardabil ・ Sardi, Iran ・ Sardi, Kerman ・ Sardi-ye Shahabad ・ Sardica paschal table ・ Sardieu ・ Sardigliano ・ Sardikhola ・ Sardinal District ・ Sardinas–Patterson algorithm ・ Sardinata ・ Sardinata River ・ Sardinata tree frog ・ Sardine ・ Sardine & Tobleroni ・ Sardine run ・ Sardine v ・ Sardinella ・ Sardinella albella ・ Sardinella atricauda ・ Sardinella brachysoma ・ Sardinella brasiliensis ・ Sardinella fijiense ・ Sardinella fimbriata Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Sardinas–Patterson algorithm ： ウィキペディア英語版 Sardinas–Patterson algorithm In coding theory, the Sardinas–Patterson algorithm is a classical algorithm for determining in polynomial time whether a given variable-length code is uniquely decodable, named after August Albert Sardinas and George W. Patterson, who published it in 1953. The algorithm carries out a systematic search for a string which admits two different decompositions into codewords. As Knuth reports, the algorithm was rediscovered about ten years later in 1963 by Floyd, despite the fact that it was at the time already well known in coding theory.〔Knuth (2003), p. 2〕 ==Idea of the algorithm== Consider the code $\backslash$. This code, which is based on an example by Berstel,〔Berstel et al. (2009), Example 2.3.1 p. 63〕 is an example of a code which is not uniquely decodable, since the string :011101110011 can be interpreted as the sequence of codewords :01110 – 1110 – 011, but also as the sequence of codewords :011 – 1 – 011 – 10011. Two possible decodings of this encoded string are thus given by ''cdb'' and ''babe''. In general, a codeword can be found by the following idea: In the first round, we choose two codewords $x\_1$ and $y\_1$ such that $x\_1$ is a prefix of $y\_1$, that is, $x\_1w\; =\; y\_1$ for some "dangling suffix" $w$. If one tries first $x\_1=011$ and $y\_1=01110$, the dangling suffix is $w\; =\; 10$. If we manage to find two sequences $x\_2,\backslash ldots,x\_p$ and $y\_2,\backslash ldots,y\_q$ of codewords such that $x\_2\backslash cdots\; x\_p\; =\; wy\_2\backslash cdots\; y\_q$, then we are finished: For then the string $x\; =\; x\_1x\_2\backslash cdots\; x\_p$ can alternatively be decomposed as $y\_1y\_2\backslash cdots\; y\_q$, and we have found the desired string having at least two different decompositions into codewords. In the second round, we try out two different approaches: the first trial is to look for a codeword that has ''w'' as prefix. Then we obtain a new dangling suffix ''w, with which we can continue our search. If we eventually encounter a dangling suffix that is itself a codeword (or the empty word), then the search will terminate, as we know there exists a string with two decompositions. The second trial is to seek for a codeword that is itself a prefix of ''w''. In our example, we have $w\; =\; 10$, and the sequence ''1'' is a codeword. We can thus also continue with ''w'=0'' as the new dangling suffix. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Sardinas–Patterson algorithm」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.